package a.codetop;

import 其他.DataStructure.ListNode;

public class _1反转链表 {
    //递归
    public ListNode reverseList(ListNode head) {
        if(head==null)return null;
        back(head);
        head.next=null;
        return nH;
    }
    ListNode nH = null;
    private ListNode back(ListNode cur) {
        if(cur.next==null){
            nH=cur;
            return cur;
        }
        ListNode fa =back(cur.next);
        fa.next=cur;
        return cur;
    }

    //迭代
    public ListNode reverseList2(ListNode head) {
        ListNode fir=head;if(fir==null)return null;
        ListNode sec=head.next;

        while(sec!=null){
            ListNode tmp = sec.next;
            sec.next=fir;
            //2点移动(tmp在w内算
            fir=sec;sec=tmp;
        }
        head.next=null;
        return fir;
    }
}
